package leetcode;

import java.util.Arrays;

/**
 * @创建人 MBY381
 * @创建时间 2022/4/20 20:11
 * @描述 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
 *
 *
 *
 * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
 */
public class Solution_jz039 {

    /**
     * 排序解法
     *
     * @param nums
     * @return
     */
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[(nums.length-1)/2];
    }

    /**
     * 官方高端解法摩尔投票
     * @param nums
     * @return
     */
    public int majorityElement1(int[] nums) {
        int count = 0;
        Integer candidate = null;

        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;
        }

        return candidate;
    }
}
